活躍する圏論 - 具体例から学ぶアプローチ
ログ
メモ
https://gyazo.com/e1d81f74c2b1e7f1f5120d6f26a768ed
メモ参照
集合$ Aについて，次の条件を満たす$ A上の関係$ \simは同値関係であるという． 1. 反射律: 任意の$ a \in Aに対して$ a \sim a 2. 推移律: 任意の$ a,b,c \in Aに対して$ a \sim b, b \sim c \implies a \sim c 3. 対称律: 任意の$ a,b \in Aに対して$ a \sim b \iff b \sim a 定理
集合$ Aの分割方法と$ A上の同値関係には1:1対応がある
https://gyazo.com/a788be268118e7d5bb600c43b97ab9a6
メモ参照．
集合$ Pについて，次のような関係$ \leqを持つ構造$ \lang P, \leq \rangは擬順序と呼ぶ． $ x,y,z \in Pとする．
2. 推移律: $ x \leq y \land y \leq z \implies x \leq z $ x \leq y \land y \leq xのとき，$ x \cong yと書いて同値であると呼ぶ．
定義: 離散擬順序(discrete preorder)（メモには書いてない） 任意の集合$ Xについて次の擬順序$ \lang X, \leq\rangが定まり，それは離散擬順序$ \lang X, = \rangであると呼ばれる． $ \leqは$ x \leq xだけを満たす．$ xでないどの要素$ y \in Xについて$ x \leq yまたは$ y \leq xを満たすことはない．
その意味で$ \leqは$ =である．
擬順序$ \lang P,\leq \rangが更に次のことを満たすなら，$ \lang P,\leq \rangは半順序と呼ぶ． $ x \leq y \land y \leq x \implies x = y
同じことだが$ x \cong y \implies x = y
注意
任意のグラフから擬順序が得られる．
https://gyazo.com/a78dfdd1cb0bf5b87f828e8b4324da45
$ Aの分割$ \{A_p\}_{p \in P}の全ての集合$ \mathfrak{Prt}(A)を順序付けることについて
https://gyazo.com/b90091b2cb5396975ea4dc433ac226fe
インフォーマルな説明
擬順序の関係（構造）を保つ ような写像のことである
写像$ f: P \to Qが擬順序$ \lang P, \leq_P\rang,\lang Q, \leq_Q\rangの単調写像であるなら
任意の$ x,y \in Pに対して
$ x \leq_P y$ \implies$ f(x) \leq_Q f(y)
$ Pは有限集合であるとする．
$ Pの冪集合$ \mathfrak{P}(P)には擬順序を定めることが出来る．
冪集合の要素$ A \in \mathfrak{P}(P)の個数を数えるような写像$ |\cdot|: \mathfrak{P}(P) \to \Nは単調写像である．
写像$ |\cdot|は濃度と呼ばれる．
擬順序$ \lang P,\leq \rangに対して$ Pの上方集合$ Uとは
$ Uは$ Pの部分集合である（$ U \sube P）
$ p \in Uかつ$ p \leq q$ \implies$ q \in U
$ U \sube X \land (\forall u \in U.\forall p \in P. (u \leq p \to p \in U))
注意: 上方集合の集合の順序
$ Pの全ての上方集合の集合を$ \mathfrak{Up}(P)と書くとする．
$ U,V \in \mathfrak{Up}(P)として$ U \sube Vであることを$ U \leq Vと表せば$ \mathfrak{Up}(P)にも順序を定めることが出来る．
https://gyazo.com/dac46d0c53de730b10ba6b3d9ec4cd41
擬順序$ \lang P,\leq \rangに対して逆擬順序$ \lang P,\leq^{\mathrm{op}}\rangとは
任意の$ p,q \in Pに対して
$ p \leq q \iff q \leq^\mathrm{op} p
https://gyazo.com/3805758e0610d4112cfcc44f972d6342
定理
任意の擬順序の恒等写像は単調写像である．
定理
任意の擬順序$ \lang P, \leq_P\rang,\lang Q, \leq_Q\rang,\lang R, \leq_R\rangに対して，
単調写像$ f: P \to Qと$ g:Q \to Rの合成$ f;g: P \to Rは単調である．
ダガー擬順序$ \lang P,\leq\rangとは要するに$ \leqが同値関係である擬順序のことである 定義: 同型写像(isormorphism)及び同型(isomorphic)について 擬順序$ \lang P,\leq_P\rangと$ \lang Q,\leq_Q\rangについて
単調写像$ f: P \to Qに対して
$ f;g = \mathrm{id}_Pかつ$ g;f = \mathrm{id}_Qな単調写像$ g: Q \to Pが存在するなら
$ Pと$ Qは同型であるという．
そのような$ gは同型写像であるという．逆写像とも言う．?
SnO2WMaN.iconこの辺はなんか用語がバラバラすぎる
https://gyazo.com/901070a5c2d07a9796871276728097ff
定義: 交わり(meet)と結び(join)について 擬順序$ \lang P,\leq \rang及び$ Pの部分集合$ Aについて，
$ pが$ Pと$ Aの交わりであるとは次のことを満たす
1. 全ての$ a \in Aに対して$ p \leq a
2. 全ての$ a \in Aに対して$ q \leq aな任意の$ qに対して，$ q \leq p
$ p = \wedge A，$ p = \wedge_{a \in A} a，$ p = \wedge_A aと表す．
$ A = \{a,b\}のように2要素なら$ \wedge Aを$ a \wedge bと表す．
$ pが$ Pと$ Aの結びであるとは次のことを満たす．
1. 全ての$ a \in Aに対して$ p \leq a
2. 全ての$ a \in Aに対して$ q \leq aな任意の$ qに対して，$ q \leq p
$ p = \vee A，$ p = \vee_{a \in A} a，$ p = \vee_A aと表す．
$ A = \{a,b\}のように2要素なら$ \vee Aを$ a \vee bと表す．
注意
離散擬順序を考えればわかるが交わりや結びは必ずしも常には存在しない． 交わりや結びは複数あり得る．
https://gyazo.com/f05c6add80c71434c551eff1a570646d
定理
擬順序$ \lang P,\leq \rang，部分集合$ A \sube B \sube Pとしたとき
$ Aと$ Bが両方交わりを持っているなら$ \wedge B \leq \wedge A
$ Aと$ Bが両方結びを持っているなら$ \vee A \leq \vee B
証明
$ \wedge B \leq \wedge Aについて
$ m \coloneqq \wedge A,n \coloneqq \wedge Bとする
任意の$ a \in Aに対して$ a \in B
$ nは$ Bの下界であるので$ Aの下界でもある
$ mは$ Aの最大下界なので，$ n \leq m
$ \vee A \leq \vee Bについても同じように．
https://gyazo.com/d7c68cd6cbf8570a111cf4c58404e57b
擬順序$ Pと$ QのGalois接続とは，次を満たす単調写像$ f:P \to Qと$ g: Q \to Pの対である． 任意の$ p \in P,q\in Qに対して，$ f(p) \leq q \iff p \leq g(q)
実験
https://gyazo.com/96bfdfd67d737bd3b8be53623790cc66
https://gyazo.com/4ccee5108004b70a49f431f252c91349https://gyazo.com/e890f485622e06e551abe914f7aa0247https://gyazo.com/9ae302512121e8828e0f71fe4338dbd5
https://gyazo.com/5a41270b06d2e41ab08fee39b51df4b2
命題
単調写像$ f:P \to Qと$ g:Q \to Pについて，1と2は同値
1: $ fと$ gがGalois接続をなして，$ fは$ gの左随伴または$ gは$ fの右随伴
2: 全ての$ p \in P,q \in Qに対して
$ p \leq g(f(p))かつ$ f(g(q)) \leq q
証明: メモ参照
定理: 右随伴が交わりを保つ / 左随伴が結びを保つ
$ f:P \to Qが$ g:Q \to Pに対する左随伴である，すなわち$ gが$ fに対する右随伴であるとき，
$ A \sube Qとして集合$ g(A) \coloneqq \{g(a) \mid a \in A \}とする．
$ Aが交わり$ \wedge A \in Qを持つなら
$ Pで$ g(A)は交わり$ \wedge g(A)を持っていて$ g(\wedge A) \cong \wedge g(A)が成り立つ．
$ A \sube Pとして集合$ f(A) \coloneqq \{f(a) \mid f \in A \}とする．
$ Aが結び$ \wedge A \in Pを持つなら
$ Qで$ f(A)は結び$ \vee g(A)を持っていて$ g(\vee A) \cong \vee g(A)が成り立つ．
証明
メモ参照
https://gyazo.com/1c16879e567a4a42f20ee2a263adb3aa
注意: 右随伴は結びを常には保たない / 左随伴は交わりを常には保たない
メモ参照
https://gyazo.com/f386d67ded21c10e024a0d5602f57a1e
定理
全ての交わりを持つ擬順序$ Qと，任意の擬順序$ Pに対して，
単調写像$ g:Q \to Pが交わりを持つ$ \iff$ gは右随伴
証明
$ \impliedby: 右随伴が交わりを保つ定理より．
$ \implies: メモ参照．
https://gyazo.com/ebf06217feb0edd8b76582fba4b0e495
関数$ A \to Bに対して
引き戻し関数$ f^*:\mathcal{P}(B) \to \mathcal{P}(A)
左随伴$ f_!:\mathcal{P}(A)\to\mathcal{P}(B)
$ f_!(A') \coloneqq \{ b \in B \mid \exists a \in A'. f(a) = b\}
右随伴$ f_*:\mathcal{P}(A)\to\mathcal{P}(B)
$ f_*(A') \coloneqq \{ b \in B \mid \forall a \in A'. f(a) = b\}
以上の$ f^*,f_!,f_*が$ fによって勝手に定まってくれる
https://gyazo.com/06e5aa9eb7ba8b1845a13881e4c2e4a6
準備
$ g:Q\to Pに対する左随伴$ f:P \to QによるGalois接続を考えると，
合成$ f;g:P\to Pという単調写像があって，次を満たす
任意の$ p \in Pに対して
1. $ p \leq (f;g)(p)
2. $ (f;g;f;g)(p) \cong (f;g)(p)
擬順序$ Pの閉包演算子とは次を満たす単調写像$ j:P\to Pである．
任意の$ p \in Pに対して
1. $ p \leq j(p)
2. $ j(j(p)) \cong j(p)
式の集合を$ \mathrm{Expr}とする
例えば，
$ \mathtt{3+4} \in \mathrm{Expr}
$ \mathtt{7} \in \mathrm{Expr}
$ \mathtt{3+4}は$ \mathtt{7}に書き換えることが出来るので，$ \rightsquigarrowという記号を用いて$ \mathtt{3+4} \rightsquigarrow \mathtt{7}といった順序がある．
このように，$ \mathrm{Expr}には書き換え可能か？によって順序を持たせることが出来る．
今，書き換えプログラム$ \piについて考えると，$ \piは閉包演算子であることが望ましい．
任意の式$ e_1,e_2,e \in \mathrm{Expr}について
0. $ e_1 \rightsquigarrow e_2$ \implies$ \pi(e_1) \rightsquigarrow \pi(e_2)
$ \piは単調性を持つ．
すなわち$ e_1が$ e_2に書き換えることが出来るなら，書き換えた結果である式$ \pi(e_1)は式$ \pi(e_2)へと書き換えることが出来る．
1. $ e \rightsquigarrow \pi(e)
$ \piによって式$ eは式$ \pi(e)という式にだけ書き換えることが出来るということを表す．
2. $ \pi(\pi(e)) \cong \pi(e)
式$ eを書き換えた式$ \pi(e)をもう一回書き換えても何も起こらない．